package day16;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/16 11:31
 */

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 给你一个非空的字符串 s 和一个整数 k ，你要将这个字符串 s 中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离 至少 为 k 。如果无法做到，请返回一个空字符串 ""。
 *
 *
 *
 * 示例 1：
 *
 * 输入: s = "aabbcc", k = 3
 * 输出: "abcabc"
 * 解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
 * 示例 2:
 *
 * 输入: s = "aaabc", k = 3
 * 输出: ""
 * 解释: 没有办法找到可能的重排结果。
 * 示例 3:
 *
 * 输入: s = "aaadbbcc", k = 2
 * 输出: "abacabcd"
 * 解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。
 */
public class Solution2 {
    public String rearrangeString(String s, int k) {
        if(k==0){
            return s;
        }
        int []cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c-'a']++;
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]) {
                    return o1[0]-o2[0];
                } else {
                    return o2[1]-o1[1];
                }
            }
        });
        for (int i = 0; i < 26; i++) {
            if(cnt[i]!=0){
                pq.add(new int[]{i,cnt[i]});
            }
        }
        LinkedList<int[]> list= new LinkedList<>();
        StringBuilder str = new StringBuilder();
        while (!pq.isEmpty()){
            for (int i = 0; i < k; i++) {
                if(pq.isEmpty()){
                    if(list.isEmpty()){
                        return str.toString();
                    }else {
                        return "";
                    }
                }
                int[] poll = pq.poll();
                str.append((char) poll[0]+'a');
                if(--poll[1]!=0){
                    list.add(poll);
                }
            }
            while (!list.isEmpty()){
                pq.add(list.removeLast());
            }
        }
        return str.toString();
    }
}
